package codingPractice.huawei;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

/*
露天矿采矿作业的特点是规模大，矿石和废料的移动量达到百万吨，运输成本开销较大，需要寻求一种最优的运输路径节省成本。
已知矿场可以划分成N*M的网格图，每个网格存在地形的差异，因此通过不同网格时，成本开销存在差异。
网格有以下5种类型：
1、标志为'S’的网格为运输起点；
2、标志为'E”的网格为运输终点；
3、标志为'B’的网格为阻塞点，不允许通行；
4、标志为'C'的网格为检查点，矿车在运输路径中，至少需要进入一次检查点。
5、标志为‘数字”的网格，其数字表示经过该网格的成本开销。
运输矿车只能上下左右4个方向运行，不允许斜对角进入其他网格。必要时可重复进入网格。
请根据输入的网格图，寻求一条从S网格到E网格，并且至少经过一次检查点的最低成本运输路径，并输出其成本开销。

迪杰斯特拉核心：if (distance[nx][ny] > distance[x][y] + weight) {
                    distance[nx][ny] = distance[x][y] + weight;
                    pq.offer(new int[]{distance[nx][ny], nx, ny});
             }
 * 逆向思维+迪杰斯特拉。
枚举所有的C点，从C点出发跑一次迪杰斯特拉，找到C->S和C->E的最短距离即可。
 */

public class KuangcheYunshu {
    private static int n, m;
    private static String[][] matrix;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        matrix = new String[n][m];
        scanner.nextLine();
        for (int i = 0; i < n; i++) {
            matrix[i] = scanner.nextLine().split(" ");
        }
        scanner.close();
        ArrayList<int[]> C = new ArrayList<>();
        int si = 0, sj = 0, ei = 0, ej = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if ("C".equals(matrix[i][j])) {
                    C.add(new int[]{i, j});
                }
                if ("S".equals(matrix[i][j])) {
                    si = i;
                    sj = j;
                }
                if ("E".equals(matrix[i][j])) {
                    ei = i;
                    ej = j;
                }
            }
        }

        int res = Integer.MAX_VALUE;
        for (int[] c : C) {
            int ci = c[0]; int cj = c[1];
            int[][] dist = solve(ci, cj);
            if (dist[si][sj] == Integer.MAX_VALUE || dist[ei][ej] == Integer.MAX_VALUE) {
                continue;
            } else {
                res = Math.min(res, dist[si][sj] + dist[ei][ej]);
            }
        }
        if (res == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(res);
        }
    }

    private static int[][] solve(int ci, int cj) {
        //pq为最小优先队列, 比较a的第一个元素的最小值排在最前面
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        boolean[][] visited = new boolean[n][m];
        int[][] distance = new int[n][m];
        for (int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                distance[i][j] = Integer.MAX_VALUE;
            }
        }
        distance[ci][cj] = 0;
        //C点到自己的距离为0
        pq.offer(new int[]{0, ci, cj});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int x = current[1];
            int y = current[2];
            if (visited[x][y]) {
                continue;
            }           
            visited[x][y] = true;

            //四个方向
            for (int[] direction : new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0 ,-1}}) {
                int nx = x + direction[0];
                int ny = y + direction[1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && !"B".equals(matrix[nx][ny])) {
                    int weight = 0;
                    if ("C".equals(matrix[nx][ny]) || "E".equals(matrix[nx][ny]) || "S".equals(matrix[nx][ny])) {
                        weight = 0;
                    } else {
                        weight = Integer.parseInt(matrix[nx][ny]);
                    }
                    if (distance[nx][ny] > distance[x][y] + weight) {
                        distance[nx][ny] = distance[x][y] + weight;
                        pq.offer(new int[]{distance[nx][ny], nx, ny});
                    }
                }
            }
        }
        return distance;
    }
}
